package com.wss.lsl.test.driven.arithmetic.sort;

import java.util.LinkedList;

/**
 * 第二个快排算法:单方向扫描，循环实现的方式
 * 
 * @author wei.ss
 * @date 2017年3月10日
 * @copyright wonhigh.cn
 */
public class QuicklySort2<T extends Comparable<T>> extends
		AbstractQuicklySort<T> {

	public QuicklySort2(T[] data) {
		super(data);
	}

	@Override
	public T[] sort() {

		int l = 0, u = data.length - 1;
		LinkedList<Integer> stack = new LinkedList<>();
		stack.push(l);
		stack.push(u);
		T t;
		int m;
		while (true) {
			if (stack.isEmpty()) {
				break;
			}

			u = stack.pop();
			l = stack.pop();

			if (l >= u) {
				continue;
			}

			t = data[l];
			m = l;
			for (int i = l + 1; i <= u; i++) {
				if (data[i].compareTo(t) < 0) {
					swap(i, ++m);
				}
			}
			swap(l, m);

			stack.push(l);
			stack.push(m - 1);

			stack.push(m + 1);
			stack.push(u);
		}

		return data;
	}

}
